Hilbert Projection Theorem

Let HH be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and MM be a finite dimensioal subspace of HH. Then for any xHx \in H, there exists a unique yMy \in M such that

minmMxm\min_{m \in M} \|x-m\|

has a unique solution yy. In other words "we can find a unique point in MM that is closest to xx". If mm^* is the closest point to xx in MM, then xmMx-m^* \perp M.

Proof: See lecture notes.

Remark: The proof stated that m=x1m^* = x_1 is the closest point to MM. It can also be interpreted as the best approximation of xx choosen from the vectors in MM. The x2x_2 term is the error in the approximation.


Example: Let V=R2V=\mathbb{R}^2 and M=span{[1,1]T}M = \text{span}\{[1,1]^T\}. Find the best approximation of x=[4,7]Tx=[4,7]^T in MM.

Solution: We need to find mm^* such that m=α[11]m^* = \alpha \begin{bmatrix} 1 \\ 1 \end{bmatrix} and xm\|x-m^*\| is minimum.

(xm)M    <xm,m>=0mM(x-m^*) \perp M \implies <x-m^*, m> = 0 \quad \forall m \in M
<xm,[11]>=0<x-m^*, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Replace x and m with their values.\text{Replace $x$ and $m^*$ with their values.}
<[4α7α],[11]>=0<\begin{bmatrix} 4-\alpha \\ 7-\alpha \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
4α+7α=04-\alpha + 7-\alpha = 0
α=112\alpha = \frac{11}{2}
m=112[11]m^* = \frac{11}{2} \begin{bmatrix} 1 \\ 1 \end{bmatrix}

Example: Let xVx \in V and M=span{v1,v2}M = \text{span}\{v_1, v_2\}. Find the best approximation of xx in MM.

Solution: We need to find mm^* such that m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2 that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
<xα1v1α2v2,v1>=<x,v1>α1<v1,v1>α2<v2,v1>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_1> = <x, v_1> - \alpha_1 <v_1, v_1> - \alpha_2 <v_2, v_1> = 0
<xα1v1α2v2,v2>=<x,v2>α1<v1,v2>α2<v2,v2>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_2> = <x, v_2> - \alpha_1 <v_1, v_2> - \alpha_2 <v_2, v_2> = 0
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
[α1α2]=[<v1,v1><v2,v1><v1,v2><v2,v2>]1[<x,v1><x,v2>]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix}^{-1} \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2

Example: Let V=R3V = \mathbb{R}^3 and M=span{[1,1,1]T,[1,0,1]T}M = \text{span}\{[1,1,1]^T, [1,0,1]^T\}. Find the best approximation of x=[4,7,2]Tx=[4,7,2]^T in MM.

Solution: We need to find mm^* such that m=α1[111]+α2[101]m^* = \alpha_1 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \alpha_2 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
[3222][α1α2]=[136]\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[3222]1[136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[1113/2][136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -1 & 3/2 \end{bmatrix} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[74]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix}
m=α1v1+α2v2=7[111]4[101]=[373]m^* = \alpha_1 v_1 + \alpha_2 v_2 = 7 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 3 \end{bmatrix}

Example: Let HH be the space of square integrable functions on [π,π][-\pi , \pi ] with inner product <f,g>=ππf(t)g(t)ˉdt<f,g> = \int_{-\pi}^{\pi} f(t)\bar{g(t)}dt. Let MM be the subspace of HH, M=span{ejkt/2π}M = \text{span}\{e^{jkt}/\sqrt{2\pi}\}, k from N to Nk \text{ from } -N \text{ to } N. Note that dimension of MM is 2N+12N+1.

<fn,fm>=ππejnt2πejmt2πdt=12πππej(nm)tdt<f_n, f_m> = \int_{-\pi}^{\pi} \frac{e^{jnt}}{\sqrt{2\pi}} \frac{e^{-jmt}}{\sqrt{2\pi}} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt
If nm, then 12πππej(nm)tdt=12πej(nm)tj(nm)ππ=0\text{If $n \neq m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \frac{e^{j(n-m)t}}{j(n-m)} \Big|_{-\pi}^{\pi} = 0
If n=m, then 12πππej(nm)tdt=12πππ1dt=1\text{If $n = m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} 1 dt = 1
Therefore, <fn,fm>={1if n=m0if nm\text{Therefore, } <f_n, f_m> = \begin{cases} 1 & \text{if $n = m$} \\ 0 & \text{if $n \neq m$} \end{cases}

Now, let gHg \in H be an arbitrary function. Then g=g1+g2g = g_1 + g_2 where g1Mg_1 \in M and g2Mg_2 \in M^{\perp}. We need to find g1g_1 such that gg1\|g-g_1\| is minimum.

g1=k=NNαkejkt2π where αk=<g,fk>=ππg(t)ejkt2πdt g_1 = \sum_{k=-N}^{N} \alpha_k \frac{e^{jkt}}{\sqrt{2\pi}} \text{ where } \alpha_k = <g, f_k> = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
αk=ππg(t)ejkt2πdt \alpha_k = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
g1=k=NNππg(t)ejkt2πejkt2πdt=k=NNππg(t)12πdt=ππg(t)dt g_1 = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} \frac{e^{jkt}}{\sqrt{2\pi}} dt = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{1}{2\pi} dt = \int_{-\pi}^{\pi} g(t) dt

Example: Find the orthagonal projection of the vector [100]\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} onto the subspace M=span{[111],[111]}M = \text{span}\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\}.

Solution: We know that the projection matrix is P=B(BTB)1BTP = B(B^TB)^{-1}B^T where BB is the matrix whose columns are the basis vectors of MM. Therefore,

B=[111111]B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}
BTB=[3113]B^TB = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}
P=[111111][3113]1[111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[111111][3/81/81/83/8][111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3/8 & -1/8 \\ -1/8 & 3/8 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[1/201/20101/201/2]P = \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}
P[100]=[1/201/2]P \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

Solution of Linear Equations

Consider the linear equation expressed as

Ax=b where ACm×n,xCn,bCmAx = b \text{ where } A \in \mathbb{C}^{m \times n}, x \in \mathbb{C}^n, b \in \mathbb{C}^m

If m=nm = n, then the equation has a unique solution. If m<nm < n, then the equation has infinitely many solutions. If m>nm > n, then the equation has no solution.


Example: Let A=[1111]A = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and b=[2.21.92.11.8]b = \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution:

b?range(A) b \in^{?} \text{range}(A)
range(A)=span{[1,1,1,1]T}\text{range}(A) = \text{span}\{[1,1,1,1]^T\}
span{[1,1,1,1]T}={[a,a,a,a]TaR}\text{span}\{[1,1,1,1]^T\} = \{[a,a,a,a]^T \mid a \in \mathbb{R}\}
brange(A)b \notin \text{range}(A)

Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

Lets call this best approximation bb^*. Then, b=α[1111]b^* = \alpha \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} and Axb2\|Ax-b^*\|^2 is minimum.

B=[1111]B = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}
P=[1111][4]1[1111]P = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}
Pb=[1111][4]1[1111][2.21.92.11.8]Pb = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 4 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2.2 \\ 1.9 \\ 2.1 \\ 1.8 \end{bmatrix}
Pb=b=[2.02.02.02.0]Pb = b^* = \begin{bmatrix} 2.0 \\ 2.0 \\ 2.0 \\ 2.0 \end{bmatrix}

Example: Let A=[21212121]A = \begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} and b=[l1l2l3l4]b = \begin{bmatrix} l_1 \\ l_2 \\ l_3 \\ l_4 \end{bmatrix}. Find xx such that Ax=bAx = b.

Solution: Now, the rows of AA are linearly dependent. Therefore, AA is not full rank. Therefore, there is no exact solution. We need to find the best approximation of bb in range(A)\text{range}(A).

b=[lˉlˉlˉlˉ] where lˉ=l1+l2+l3+l44b^* = \begin{bmatrix} \bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix} \text{ where } \bar l = \frac{l_1+l_2+l_3+l_4}{4}
[21212121][x1x2]=[lˉlˉlˉlˉ]\begin{bmatrix} 2 & 1 \\ 2 & 1 \\ 2 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix}\bar l \\ \bar l \\ \bar l \\ \bar l \end{bmatrix}
[x1x2]=[lˉlˉ] is any solution, more examples [11],[23],[35],\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} \text{ is any solution, more examples } \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \begin{bmatrix} 2 \\ -3 \end{bmatrix}, \begin{bmatrix} 3 \\ -5 \end{bmatrix}, \ldots
A minimum norm solution is can be found by minimizing the norm of x.\text{A minimum norm solution is can be found by minimizing the norm of $x$.}
 For that, we can project any solution onto the null space perpendicular to A.\text{ For that, we can project any solution onto the null space perpendicular to $A$.}
x1=ProjN(A)[lˉlˉ]x_1 = \text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Corollary: N(A)=range(A)\text{Corollary: } N(A)^{\perp} = \text{range}(A^*)
A=[22221111]A^* = \begin{bmatrix} 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 1 \end{bmatrix}
range(A)=span{[21]}\text{range}(A^*) = \text{span}\bigg \{\begin{bmatrix} 2 \\ 1 \end{bmatrix}\bigg\}
ProjN(A)[lˉlˉ]=Projrange(A)[lˉlˉ]\text{Proj}_{N(A)^{\perp}} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}
Projrange(A)[lˉlˉ]=<[lˉlˉ],[21]><[21],[21]>[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{<\begin{bmatrix} \bar l \\ - \bar l \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>}{<\begin{bmatrix} 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}>} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
Projrange(A)[lˉlˉ]=lˉ5[21]\text{Proj}_{\text{range}(A^*)} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \frac{\bar l}{5} \begin{bmatrix} 2 \\ 1 \end{bmatrix}
 Or in projection matrix form, Q=[21] then, P=Q(QQ)1Q\text{ Or in projection matrix form, } Q = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \text{ then, } P = Q(Q^*Q)^{-1}Q^*
P=[21]15[21]=[4/52/52/51/5]P = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \frac{1}{5} \begin{bmatrix} 2 & 1 \end{bmatrix} = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix}
x1=Px=[4/52/52/51/5][lˉlˉ]=[4/5lˉ2/5lˉ2/5lˉ1/5lˉ]=[2/5lˉ1/5lˉ]=lˉ/5[21]x_1 = Px = \begin{bmatrix} 4/5 & 2/5 \\ 2/5 & 1/5 \end{bmatrix} \begin{bmatrix} \bar l \\ - \bar l \end{bmatrix} = \begin{bmatrix} 4/5 \bar l - 2/5 \bar l \\ 2/5 \bar l - 1/5 \bar l \end{bmatrix} = \begin{bmatrix} 2/5 \bar l \\ 1/5 \bar l \end{bmatrix} = \bar l/ 5 \begin{bmatrix} 2 \\ 1 \end{bmatrix}

#EE501 - Linear Systems Theory at METU